#include "avl_tree.h"


bool avl_tree_is_unbalanced_tree(avl_tree rt)
{
    return avl_tree_is_unbalanced_tree_imp(rt) & 1;
}
uint32_t avl_tree_is_unbalanced_tree_imp(avl_tree rt) 
{
    if (NULL == rt) {
        return 0;
    }   

    uint32_t l = avl_tree_is_unbalanced_tree(rt->left);
    uint32_t r = avl_tree_is_unbalanced_tree(rt->right);

    uint32_t ld = l >> 1;
    uint32_t rd = r >> 1;

    uint32_t left_ub = l & 1;
    uint32_t right_ub = r & 1;

    uint32_t res = ld > rd ? ld : rd;
    res = res + 1;
    res <<= 1;
    
     if ( abs(ld -rd) > 1 || left_ub || right_ub ) {
        res |= 1;
    }

    return res; 
}

uint32_t avl_tree_get_head_unbalanced_node(avl_tree rt, avl_node **p)
{
    if (NULL == rt) {
        return 0;
    }   

    uint32_t l = avl_tree_get_head_unbalanced_node(rt->left, p);
    uint32_t r = avl_tree_get_head_unbalanced_node(rt->right, p);

    uint32_t ld = l >> 1;
    uint32_t rd = r >> 1;


    uint32_t left_ub = l & 1;
    uint32_t right_ub = r & 1;

    if (*p == NULL && abs(ld-rd) > 1 ) {
        *p = rt;
    }

    uint32_t res = ld > rd ? ld : rd;
    res = res + 1;
    res <<= 1;
    
    if ( left_ub || right_ub || abs(ld - rd) > 1) {
        res |= 1;
    }


    return res; 
}

int avl_tree_get_height(avl_tree r)
{
    if (NULL == r)
        return 0;

    int ld = avl_tree_get_height(r->left);
    int rd = avl_tree_get_height(r->right);
    return ld < rd ? rd + 1 : ld + 1;
}
void avl_tree_set_child(
    avl_node **rt,
    avl_tree pa, 
    avl_tree old_child, 
    avl_tree new_child)
{
    if (NULL == pa)
        *rt = new_child ;
    else if (pa->left == old_child) {
        pa->left = new_child;
    }
    else if (pa->right == old_child) {
        pa->right = new_child;
    }
    else {
        printf("some fatal error occured!\n");
    }
}
avl_tree avl_tree_get_replace(avl_tree r)
{
    if (NULL == r)
        return NULL;
    
    avl_tree ln = r->left;
    while ( ln && ln->right)
        ln = ln->right;

    avl_tree rn = r->right;
    while ( rn && rn->left)
        rn = rn->left;

    return ln != NULL ? ln : rn;
}
bool avl_tree_delete(avl_tree *r, int dt)
{
    avl_tree del_node = avl_tree_lookup(r, dt);
    if (del_node == NULL)
        return false;

    avl_tree del_pa = avl_tree_lookup_pa( r, del_node);
    avl_tree rep_node = avl_tree_get_replace( del_node);

    if ( NULL != rep_node ) {
        avl_tree rep_pa = avl_tree_lookup_pa(r, rep_node);

        avl_tree_set_child(r, rep_pa, rep_node, NULL);

        rep_node->left  = del_node->left;
        rep_node->right = del_node->right;
    }
    avl_tree_set_child( r, del_pa, del_node, rep_node);
    

    del_node->left = NULL;
    del_node->right = NULL;
    free(del_node);

    avl_tree_adjust(r);

    return true;
}


bool avl_tree_find(avl_tree *r, int dt)
{
    return avl_tree_lookup(r, dt) != NULL;
}
avl_tree avl_tree_lookup_pa(avl_tree *r, avl_tree tag)
{
    if ( *r == NULL)
        return NULL;
    if ( r[0]->left == tag || r[0]->right == tag)
        return *r;

    avl_tree ln = avl_tree_lookup_pa(&(r[0]->left), tag);
    avl_tree rn = avl_tree_lookup_pa(&(r[0]->right), tag);

    return ln == NULL ? rn : ln ;
}
avl_tree avl_tree_lookup(avl_tree *r, int data)
{
    avl_tree rt = *r;

    while (rt) {
        if (data > rt->data) {
            rt = rt->right;
        }
        else if (data < rt->data) {
            rt = rt->left;
        }
        else 
            break;
    }

    return rt;
}

/*return root node of avl tree*/
avl_tree avl_tree_insert(avl_tree *r, int data) 
{
    avl_tree *pos = r;


    while (*pos) {
        if (pos[0]->data == data) {
            return *r;
        }
        else if (pos[0]->data < data){
            pos = &(pos[0]->right);
        }
        else {
            pos = &(pos[0]->left);
        }
    }

    avl_tree nd = (avl_tree) malloc(sizeof(avl_node));
    nd->left = nd->right = NULL;
    nd->data = data;
    *pos = nd;
   
    avl_tree_adjust(r);


    return *r;
}
/*avl delete all */
void avl_tree_free(avl_tree *r)
{
    if ( NULL == r[0])
        return ;
    avl_tree_free(&(r[0]->left));
    avl_tree_free(&(r[0]->right));

    free(*r);
}
/* 
tree adjust
*/
/* lll adjust: RotateR*/
/*
          p                           p
          |                           |
          A                           B
        /  \      --->              /  \
       B    X                      C    A
     /  \                              / \ 
    C    Y                           Y    X   

before RotateR( A )
 1). let |tree_node| = height(tree_node)
 2). |B| = |X| + 2  ,|C| = |X| + 1, |Y| = {|X|, |X| - 1}

after RotateL( A )
    |A| = |X| + 1
*/
avl_tree avl_tree_RotateR(avl_tree head)
{
    avl_tree A = head;
    avl_tree B = head->left;
    avl_tree C = B->left;

    avl_tree X = head->right;
    avl_tree Y = B->right;

    A->left  = Y;
    B->right = A; 

    return B;
}
/* rrr: RotateL*/

/*
          p                           p
          |                           |
          A                           B
        /  \      --->              /  \
      X     B                      A    C
          /  \                   /  \    
        Y     C                X     Y      
before RotateL( A )
 1). let |tree_node| = height(tree_node)
 2). |B| = |X| + 2  ,|C| = |X| + 1, |Y| = {|X|, |X| - 1}

after RotateL( A )
    |A| = |X| + 1
*/
avl_tree avl_tree_RotateL(avl_tree head)
{
    avl_tree A = head;
    avl_tree B = head->right;
    avl_tree C = B->right;

    avl_tree X = A->left;
    avl_tree Y = B->left;

    B->left = A;
    A->right = Y;

    return B;
}
/* lr adjust*/
/*

                                     
            p                                       
            |                            
            A                         B                                      C
          /  \                      /  \       RotateL( B )                /  \
        B     X    --->           Y     C     ==============>            B     W    
      /  \                             / \                             / \
    Y     C                           Z   W                          Y    Z
         / \
        Z   W

before RotateL( B )
 1). let |tree_node| = height(tree_node)
 2). |B| = |x| + 2  ,|C| = |X| + 1, |Y| = {|X|, |X| - 1}
 3). case 1.  |Z| = |X|, |W| = |X| - 1
     case 2.  |Z| = |X| - 1, |W| = |X|
after RotateL( B )
     case 1. |Z| = |X|, |B| = |X| + 1, |C| = |X| + 2
     case 2. |Z| = |X| - 1,|B| = |Y| + 1, |C| = |Y| + 2
     
            P                                                     P
            |                                                     |
            A                                                     C
          /  \         RotateR(A)                               /   \
        C     X    ================>                          B      A
      /  \                                                  /  \    / \
    B     W                                                Y    Z  W   X
   / \ 
 Y    Z
*/
avl_tree avl_tree_RotateLR(avl_tree head)
{
    avl_tree A = head;
    avl_tree B = head->left;
    avl_tree C = B->right;

    A->left = avl_tree_RotateL(B);

    return avl_tree_RotateR(A);
}
/* rl adjust*/
/*

                                     
            p                                       
            |                            
            A                         B                                      C
          /  \                      /  \       RotateR( B )                /  \
        X     B         --->       C    Y     ==============>            Z     B         
            /  \                  / \                                         / \
           C    Y                Z   W                                       W    Y
         / \
       Z    W
before RotateL( B )
 1). let |tree_node| = height(tree_node)
 2). |B| = |x| + 2  ,|C| = |X| + 1, |Y| = {|X|, |X| - 1}
 3). case 1.  |Z| = |X|, |W| = |X| - 1
     case 2.  |Z| = |X| - 1, |W| = |X|
after RotateL( B )
     case 1. |Z| = |X|, |B| = |X| + 1, |C| = |X| + 2
     case 2. |Z| = |X| - 1,|B| = |Y| + 1, |C| = |Y| + 2

     
            P                                                     P
            |                                                     |
            A                                                     C
          /  \         RotateR(A)                               /   \
        C     X    ================>                          B      A
      /  \                                                  /  \    / \
    B     W                                                Y    Z  W   X
   / \ 
 Y    Z
*/
avl_tree avl_tree_RotateRL(avl_tree head)
{
    avl_tree A = head;
    avl_tree B = head->right;
    avl_tree C = B->left;

    A->right = avl_tree_RotateR(B);

    return avl_tree_RotateL(A);
}
int getGrandSonHeight(avl_tree a, bool is_left_tree, bool get_right)
{

    if ( is_left_tree )
        a = a->left;
    else 
        a = a->right;
    
    if ( get_right )
        return avl_tree_get_height(a->right);
    else
        return avl_tree_get_height(a->left);
}
int avl_tree_get_ub_type(avl_tree head_ub_node)
{   

    avl_tree a = head_ub_node;
   

    int ld = avl_tree_get_height(a->left);
    int rd = avl_tree_get_height(a->right);


    if ((ld - rd != 2) && (rd - ld != 2)) {
        printf("some error occurred!!!\n");
        return AVL_NORMAL;
    }
    bool is_left_tree = ld - rd == 2 ? true : false;
    int r2d = getGrandSonHeight(a, is_left_tree, AVL_TREE_RIGHT_TREE);
    int l2d = getGrandSonHeight(a, is_left_tree, AVL_TREE_LEFT_TREE);

    int ret = ld >  rd ? 0 : 2;
    ret  |=  (l2d > r2d ? 0 : 1); 


    return ret;
}
void avl_tree_adjust(avl_tree *rt)
{
    avl_node *head_ub_node = NULL;

    uint32_t ret = avl_tree_get_head_unbalanced_node(*rt, &head_ub_node);

    if (NULL == head_ub_node)
        return ;
    avl_tree ub_pa = avl_tree_lookup_pa(rt, head_ub_node);
    avl_tree new_head = NULL;

    
    switch (avl_tree_get_ub_type(head_ub_node))
    {
        case AVL_LLL_UB:
            new_head = avl_tree_RotateR(head_ub_node);
            break;
        case AVL_RRR_UB:
            new_head = avl_tree_RotateL(head_ub_node);
            break;
        case AVL_LR_UB:
            new_head = avl_tree_RotateLR(head_ub_node);
            break;
        case AVL_RL_UB:
            new_head = avl_tree_RotateRL(head_ub_node);
            break;
        default:
            return;
    }

    avl_tree_set_child(rt, ub_pa, head_ub_node, new_head);
}